package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/07/25 11:25
 **/
public class Day10_2_Num24_SwapPairs {
    // 方法一：三指针法
    class Solution {
        public ListNode swapPairs(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
            ListNode cur = dummyHead;     // 指向需要交换节点的前一个结点
            ListNode first = head;        // 指向前一个节点
            ListNode second = head.next;  // 指向后一个节点
            while(first != null){
                first.next = second.next;
                second.next = first;
                cur.next = second;

                cur = first;
                first = first.next;
                if(first != null && first.next != null){
                    second = first.next;
                }else {
                    return dummyHead.next;
                }
            }
            return dummyHead.next;
        }
    }

    // 方法二：递归
    class Solution2 {
        public ListNode swapPairs(ListNode head) {
            // 结束条件
            if(head == null || head.next == null){
                return head;
            }
            // （根据代码画图一看便知）
            ListNode next = head.next;
            head.next = swapPairs(next.next);
            next.next = head;

            return next;
        }
    }
}